package fibonacci;

/**
 * Created with IntelliJ IDEA.
 * Description:给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。
 * 一且你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 * User: YJ
 * Date: 2023-9-21
 * Time: 8:28
 */
public class Fibonacci2 {
    public static int  fibonacci(int[] cost) {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        //处理边界
        if (cost.length == 0 || cost.length == 1) return 0;
        int[] dp = new int[cost.length + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = (dp[i - 1] + cost[i - 1]) < (dp[i - 2] + cost[i - 2]) ? (dp[i - 1] + cost[i - 1]) : (dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

    public static int  fibonacci2(int[] cost) {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        //处理边界
        int n  =cost.length;
        if (n == 0 || n == 1) return 0;
        int[] dp = new int[n];
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0 ; i--) {
            dp[i] = Math.min(dp[i - 1],dp[i - 2]) + cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }

    public static void main(String[] args) {
        int[] cost = new int[3];
        cost[0] = 5;
        cost[1] = 15;
        cost[2] = 20;
        System.out.println(fibonacci(cost));
    }
}
